#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define USERS 500
#define MOVIES 50
#define DATALINES 9997	

#define NCOMMUSER 2

typedef struct s_data {
	int user;
	int movie;
	int rating;
} Data;

typedef struct s_corr_temp {
	float sum_i, sum_j, sum_ij, sum_ii, sum_jj, count;
} CorrelationTemp;

typedef struct s_sort_temp {
	float corr;
	int index;
} SortTemp;

int byuser_compare(const void *arg1, const void *arg2) {
	Data a, b;
	a = *(Data *)arg1;
	b = *(Data *)arg2;
	
	if (a.user < b.user) return -1;
	else if (a.user > b.user) return 1;
	else {
		if (a.movie < b.movie) return -1;
		else if (a.movie > b.movie) return 1;
		else return 0;
	}
}

int bymovie_compare(const void *arg1, const void *arg2) {
	Data a, b;
	a = *(Data *)arg1;
	b = *(Data *)arg2;
	
	if (a.movie < b.movie) return -1;
	else if (a.movie > b.movie) return 1;
	else {
		if (a.user < b.user) return -1;
		else if (a.user > b.user) return 1;
		else return 0;
	}
}

int corr_compare(const void *arg1, const void *arg2) {
	SortTemp a, b;
	a = *(SortTemp *)arg1;
	b = *(SortTemp *)arg2;
	
	float acorr = fabs(a.corr);
	float bcorr = fabs(b.corr);
	
	if (acorr < bcorr) return 1;
	else if (acorr > bcorr) return -1;
	else return 0;
}

int main(int argc, char *argv[]) {
	FILE *in;
	
	// temporary
	int user, movie;
	int rating;
	char temp[100];
	
	int i, j, k, u, l;
	int counter;
	
	// storage
	Data raw[DATALINES];
	Data byuser[DATALINES];
	Data bymovie[DATALINES];
	int mindex[MOVIES + 1];
	int uindex[USERS + 1];
	
	// correlation-related
	float corr[MOVIES][MOVIES];
	CorrelationTemp corrvars[MOVIES];
	int current_movie, current_user, current_rating;
	int second_movie;
	float denominator;
	
	// knn
	int predict_user, predict_movie;
	float predict_movie_corr[MOVIES];
	SortTemp sortcorrs[MOVIES];
	int knn = 5;
	float prediction;
	int predictions;
	
	// initialising to 0
	memset( mindex, '\0', sizeof(mindex) );
	memset( uindex, '\0', sizeof(uindex) );
	memset( corr, '\0', sizeof(corr) );
	
	//
	// read in
	//
	in = fopen("toydata4.txt", "r");
	
	counter = 0;
	while ( fscanf(in, "%d,%d,%d", &user, &movie, &rating) != EOF ) {
		raw[counter].user = byuser[counter].user = bymovie[counter].user = user;
		raw[counter].movie = byuser[counter].movie = bymovie[counter].movie = movie;
		raw[counter].rating = byuser[counter].rating = bymovie[counter].rating = rating;
		mindex[movie + 1]++;
		uindex[user + 1]++;
		counter++;
	}
	
	for (i = 1; i < MOVIES; i++) {
		// if (mindex[i] == 0)
			mindex[i] = mindex[i] + mindex[i-1];
		//else
		//	mindex[i] = -1;
		// printf("%d %d\n", i, mindex[i]);
	}
	for (i = 1; i < USERS; i++) {
		//if (uindex[i] != 0)
			uindex[i] = uindex[i] + uindex[i-1];
		//else
		//	uindex[i] = -1;
	}
	
	//
	// sort
	//
	qsort(byuser, DATALINES, sizeof(Data), byuser_compare);
	qsort(bymovie, DATALINES, sizeof(Data), bymovie_compare);
	
	//
	// compute correlation matrix
	//
	for (k = 0; k < MOVIES; k++) {
		//printf("Movie %d, from %d to %d\n", k, mindex[k], mindex[k+1]-1);
	
		memset( corrvars, '\0', sizeof(corrvars) );
		
		// printf("%d ", k);
		for (i = mindex[k]; i < mindex[k+1]; i++) {
			// printf("Dataline %d : ", i);
			current_movie = bymovie[i].movie;
			current_user = bymovie[i].user;
			current_rating = bymovie[i].rating;
			// printf("%d %d %d : ", current_user, current_movie, current_rating);
			
			// printf("User %d, from %d to %d\n", current_user, uindex[current_user], uindex[current_user+1]-1);
			for (j = uindex[current_user]+1; j < uindex[current_user+1]+1; j++) {
				
				if (byuser[j].movie > current_movie) {
					second_movie = byuser[j].movie;
					// printf("Second movie %d\n", second_movie);
					
					corrvars[second_movie].sum_i += current_rating;
					corrvars[second_movie].sum_j += byuser[j].rating;
					corrvars[second_movie].sum_ij += current_rating * byuser[j].rating;
					corrvars[second_movie].sum_ii += current_rating * current_rating;
					corrvars[second_movie].sum_jj += byuser[j].rating * byuser[j].rating;
					corrvars[second_movie].count += 1;
				}
			}
		}
		
		
		for (i = k+1; i < MOVIES; i++) {
			/*printf("Second movie %d\n", i);
			printf("Sum_i %d ", corrvars[i].sum_i);
			printf("Sum_j %d ", corrvars[i].sum_j);
			printf("Sum_ij %d ", corrvars[i].sum_ij);
			printf("Sum_ii %d ", corrvars[i].sum_ii);
			printf("Sum_jj %d ", corrvars[i].sum_jj);
			printf("Count %d ", corrvars[i].count);
			printf("\n");*/
			
			denominator = 
					sqrt( (corrvars[i].sum_ii - ((corrvars[i].sum_i*corrvars[i].sum_i)/corrvars[i].count))
						* (corrvars[i].sum_jj - ((corrvars[i].sum_j * corrvars[i].sum_j)/corrvars[i].count)) );
			if (denominator != 0)
					corr[i][k] = (corrvars[i].sum_ij - ((corrvars[i].sum_i * corrvars[i].sum_j)/corrvars[i].count)) / denominator;
				else 
					corr[i][k] = 0;
			corr[k][i] = corr[i][k];
		}
	}
	
	//
	// simple knn
	//
	
	srand48(104920);
	
	predictions = 50;
	for (l = 0; l < predictions; l++) {
		predict_movie = (int) (drand48() * MOVIES);
		predict_user = (int) (drand48() * USERS);
	
		for (i = 0; i < MOVIES; i++) {
			sortcorrs[i].index = i;
			sortcorrs[i].corr = corr[i][predict_movie];
		}
		qsort(sortcorrs, MOVIES, sizeof(SortTemp), corr_compare);
		
		prediction = 0;
		j = 0;
		for (i = 0; i < MOVIES; i++) {
			// prediction += byuser[uindex[predict_user]] [sortcorrs[i].index];
			for (k = uindex[predict_user]; k < uindex[predict_user+1]; k++) {
				if (byuser[k].movie == sortcorrs[i].index) {
					prediction += byuser[k].rating;
					j++;
					break;
				}
			}
			if (j >= knn)
				break;
		}
		prediction /= knn;
		printf("%d %d %f\n", predict_user, predict_movie, prediction);
	}
	
	//
	// output
	//
	if (0) {
		for (i = 0; i < DATALINES; i++) {
			 printf("%d %d %d \n", byuser[i].user, byuser[i].movie, byuser[i].rating);
			// printf("%d %d %d \n", bymovie[i].user, bymovie[i].movie, bymovie[i].rating);
		}
	}
	if (0) {
		for (i = 0; i < USERS; i++) {
			printf("%d %d\n", uindex[i], bymovie[uindex[i]].user);
		}
	}
	if (0) {
		int temp;
		printf("\n");
		for (i = mindex[2]; i < mindex[3]; i++) {
			
			printf("%d %d %d\n", bymovie[i].user, bymovie[i].movie, byuser[i].rating);
		}
	}
	

	return 0;
}
